#ifndef REGION_GROWING
#define REGION_GROWING

#define SIGMA 1
#define DIFF_PIX 1
#define INTERVAL 40
#define DIFF_REG 4

#define USE_FILTER
#define USE_MERGE

#include <cstdlib>
#include <iostream>
#include <image.h>
#include <filter.h>
#include <queue>

using namespace std;

queue<long> p;
int regionCounter = 0;

inline int getW(long val){
	return (int)(val/10000);
}// get width

inline int getH(long val){
	return (int)(val%10000);
}// get height

rgb random_rgb(){ 
  rgb c;
  double r;
  c.r = (uchar)random();
  c.g = (uchar)random();
  c.b = (uchar)random();
  return c;
}// random color

double calGray(image<rgb> *im, int w, int h){
	int r = imRef(im, w, h).r;
	int g = imRef(im, w, h).g;
	int b = imRef(im, w, h).b;
	return r * 0.2126 + g * 0.7152 + b * 0.0722;
}// compute the val gray


int similarPixel(image<rgb> *im, int w, int h, int w1, int h1) {

	double gray = calGray(im, w, h);
	double gray1 = calGray(im, w1, h1);
	
	double diff = gray - gray1;

	if(diff < DIFF_PIX && diff > -DIFF_PIX)
		return 1;
	else
		return 0;

}// test two pixels to return 1 for similar, 0 for not similar


int similarRegion(double regVal1, double regVal2) {

	double diff = regVal1 - regVal2;
	if(diff < DIFF_REG && diff > -DIFF_REG)
		return 1;
	else
		return 0;

}// test two regions to return 1 for similar, 0 for not similar


void testNeighborPixel(image<rgb> *im, image<int> *imRegNo, image<int> *imRegPixSum, image<double> *imRegValSum, int regNo, int w, int h){

	int width = im->width();
	int height = im->height();

  if (w < width-1) {
    /* right top */
    if (h > 0) {
    	if(imRef(imRegNo, w+1, h-1)==0)	{
		  	if(similarPixel(im, w, h, w+1, h-1)) {
		  		imRef(imRegNo, w+1, h-1) = regNo;
					imRef(imRegPixSum, (int)regNo%width, (int)regNo/width)++;
		  		imRef(imRegValSum, (int)regNo%width, (int)regNo/width)+=calGray(im, w+1, h-1);
		  		//if(!p.Find((w+1)*10000+(h-1)))
		  			p.push((w+1)*10000+(h-1));
		  		//testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regNo, w+1, h-1);
		  	}
			}
    }
    /* right middle */
    if(imRef(imRegNo, w+1, h)==0) {
			if(similarPixel(im, w, h, w+1, h)) {
		  	imRef(imRegNo, w+1, h) = regNo;//printf("rm %dw %dh\t", w, h);
				imRef(imRegPixSum, (int)regNo%width, (int)regNo/width)++;
		  	imRef(imRegValSum, (int)regNo%width, (int)regNo/width)+=calGray(im, w+1, h);
		  	//if(!p.Find((w+1)*10000+(h)))
		  		p.push((w+1)*10000+(h));
		  	//testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regNo, w+1, h);
			}
		}
    /* right bottom */
    if (h < height-1) {
    	if(imRef(imRegNo, w+1, h+1)==0) {
				if(similarPixel(im, w, h, w+1, h+1)) {
		  		imRef(imRegNo, w+1, h+1) = regNo;//printf("rb %dw %dh\t", w, h);
					imRef(imRegPixSum, (int)regNo%width, (int)regNo/width)++;
		  		imRef(imRegValSum, (int)regNo%width, (int)regNo/width)+=calGray(im, w+1, h+1);
		  		//if(!p.Find((w+1)*10000+(h+1)))cout<<"OOOO"<<endl;
		  			p.push((w+1)*10000+(h+1));
		  		//testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regNo, w+1, h+1);
		  	}
    	}
    }
  }// test the right

  if (h > 0) {
  	if(imRef(imRegNo, w, h-1)==0) {
			if(similarPixel(im, w, h, w, h-1)) {
				imRef(imRegNo, w, h-1) = regNo;//printf("mt %dw %dh\t", w, h);
				imRef(imRegPixSum, (int)regNo%width, (int)regNo/width)++;
				imRef(imRegValSum, (int)regNo%width, (int)regNo/width)+=calGray(im, w, h-1);
				//if(!p.Find((w)*10000+(h-1)))
					p.push((w)*10000+(h-1));
				//testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regNo, w, h-1);
			}
  	}
  }/* middle top */

  if (h < height-1) {
  	if(imRef(imRegNo, w, h+1)==0) {
			if(similarPixel(im, w, h, w, h+1)) {
				imRef(imRegNo, w, h+1) = regNo;//printf("mb %dw %dh\t", w, h);
				imRef(imRegPixSum, (int)regNo%width, (int)regNo/width)++;
		  	imRef(imRegValSum, (int)regNo%width, (int)regNo/width)+=calGray(im, w, h+1);
		  	//if(!p.Find((w)*10000+(h+1)))
		  		p.push((w)*10000+(h+1));
				//testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regNo, w, h+1);
			}
  	}
  }/* middle bottom */

  if (w > 0) {
    /* left top */
    if (h > 0) {
    	if(imRef(imRegNo, w-1, h-1)==0) {
				if(similarPixel(im, w, h, w-1, h-1)) {
		  		imRef(imRegNo, w-1, h-1) = regNo;//printf("lt %dw %dh\t", w, h);
		  		imRef(imRegPixSum, (int)regNo%width, (int)regNo/width)++;
		  		imRef(imRegValSum, (int)regNo%width, (int)regNo/width)+=calGray(im, w-1, h-1);
		  		//if(!p.Find((w-1)*10000+(h-1)))
		  			p.push((w-1)*10000+(h-1));
		  		//testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regNo, w-1, h-1);
		  	}
    	}
    }
    /* left middle */
    if(imRef(imRegNo, w-1, h)==0) {
			if(similarPixel(im, w, h, w-1, h)) {
				imRef(imRegNo, w-1, h) = regNo;//printf("lm %dw %dh\t", w, h);
				imRef(imRegPixSum, (int)regNo%width, (int)regNo/width)++;
		  	imRef(imRegValSum, (int)regNo%width, (int)regNo/width)+=calGray(im, w-1, h);
		  	//if(!p.Find((w-1)*10000+(h)))
		  		p.push((w-1)*10000+(h));
				//testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regNo, w-1, h);
			}
  	}
    /* left bottom */
    if (h < height-1) {
    	if(imRef(imRegNo, w-1, h+1)==0) {
				if(similarPixel(im, w, h, w-1, h+1)) {
		  		imRef(imRegNo, w-1, h+1) = regNo;//printf("lb %dw %dh\t", w, h);
		  		imRef(imRegPixSum, (int)regNo%width, (int)regNo/width)++;
		  		imRef(imRegValSum, (int)regNo%width, (int)regNo/width)+=calGray(im, w-1, h+1);
		  		//if(!p.Find((w-1)*10000+(h+1)))
		  			p.push((w-1)*10000+(h+1));
		  		//testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regNo, w-1, h+1);
		  	}
    	}
    }
  }// test the left

}// Test the neighbors of a pixel, change their regNo if they are similar


void testMerge(image<int> *imRegNo, image<int> *imRegPixSum, image<double> *imRegValSum, int regNo1, int regNo2, double regVal1) {
	int width = imRegNo->width();
  int height = imRegNo->height();
	double regVal2 = imRef(imRegValSum, regNo2%width, regNo2/width)/imRef(imRegPixSum, regNo2%width, regNo2/width);
	if(similarRegion(regVal1, regVal2)) {
//		cout<<"merge: "<<regNo1<<" "<<regNo2<<endl;
		imRef(imRegValSum, regNo1%width, regNo1/width)+=imRef(imRegValSum, regNo2%width, regNo2/width);
		imRef(imRegPixSum, regNo1%width, regNo1/width)+=imRef(imRegPixSum, regNo2%width, regNo2/width);
		imRef(imRegValSum, regNo2%width, regNo2/width)=0;
		imRef(imRegPixSum, regNo2%width, regNo2/width)=0;
		for (int h = 0; h < height; h++) {
		  for (int w = 0; w < width; w++) {
		    if(imRef(imRegNo, w, h) == regNo2) {
		    	imRef(imRegNo, w, h) = regNo1;
		    }
		  }
		}
		regionCounter--;
	}
}// test to merge two regions

void testNeighborRegion(image<int> *imRegNo, image<int> *imRegPixSum, image<double> *imRegValSum, int w, int h){

	int width = imRegNo->width();
	int height = imRegNo->height();
	
	int regNo1 = imRef(imRegNo, w, h);
	double regVal1 = imRef(imRegValSum, regNo1%width, regNo1/width)/imRef(imRegPixSum, regNo1%width, regNo1/width);

  if (w < width-1) {
    /* right top */
    if (h > 0) {
    	int regNo2 = imRef(imRegNo, w+1, h-1);
    	if(regNo2!=0 && regNo2!=regNo1)
				testMerge(imRegNo, imRegPixSum, imRegValSum, regNo1, regNo2, regVal1);
			}

    /* right middle */
	  int regNo2 = imRef(imRegNo, w+1, h);
  	if(regNo2!=0 && regNo2!=regNo1)
			testMerge(imRegNo, imRegPixSum, imRegValSum, regNo1, regNo2, regVal1);
			
    /* right bottom */
    if (h < height-1) {
    	int regNo2 = imRef(imRegNo, w+1, h+1);
    	if(regNo2!=0 && regNo2!=regNo1)
				testMerge(imRegNo, imRegPixSum, imRegValSum, regNo1, regNo2, regVal1);
    }
    
  }// test the right

  if (h > 0) {
  	int regNo2 = imRef(imRegNo, w, h-1);
  	if(regNo2!=0 && regNo2!=regNo1)
			testMerge(imRegNo, imRegPixSum, imRegValSum, regNo1, regNo2, regVal1);
  }/* middle top */

  if (h < height-1) {
  	int regNo2 = imRef(imRegNo, w, h+1);
  	if(regNo2!=0 && regNo2!=regNo1)
			testMerge(imRegNo, imRegPixSum, imRegValSum, regNo1, regNo2, regVal1);
  }/* middle bottom */

  if (w > 0) {
    /* left top */
    if (h > 0) {
    	int regNo2 = imRef(imRegNo, w-1, h-1);
    	if(regNo2!=0 && regNo2!=regNo1)
				testMerge(imRegNo, imRegPixSum, imRegValSum, regNo1, regNo2, regVal1);
    }
    
    /* left middle */
    	int regNo2 = imRef(imRegNo, w-1, h);
    	if(regNo2!=0 && regNo2!=regNo1)
				testMerge(imRegNo, imRegPixSum, imRegValSum, regNo1, regNo2, regVal1);
				
    /* left bottom */
    if (h < height-1) {
    	int regNo2 = imRef(imRegNo, w-1, h+1);
    	if(regNo2!=0 && regNo2!=regNo1)
				testMerge(imRegNo, imRegPixSum, imRegValSum, regNo1, regNo2, regVal1);
    }
    
  }// test the left

}// Test the neighbors of a region, merge them


image<rgb> *segment_image(image<rgb> *im, int *regNum) {

  int width = im->width();
  int height = im->height();

  // an image imRegNo to store every pixel's region number
  // an image imRegValSum to store the sum of every region's valeur
  // an image imRegPixSum to store the sum of every region's pixels
  // imRegNo->data = 0 => this pixel don't in any region
  // imRegPixSum->data = 0 => No this region
  image<int> *imRegNo = new image<int>(width, height);
  image<double> *imRegValSum = new image<double>(width, height);
  image<int> *imRegPixSum = new image<int>(width, height);
  // initialisation imRegNo imRegValSum imRegPixSum
  for (int h = 0; h < height; h++) {
    for (int w = 0; w < width; w++) {
      imRef(imRegNo, w, h) = 0;
      imRef(imRegValSum, w, h) = 0;
      imRef(imRegPixSum, w, h) = 0;
    }
	}


#ifdef USE_FILTER
	image<float> *r = new image<float>(width, height);
  image<float> *g = new image<float>(width, height);
  image<float> *b = new image<float>(width, height);

  // smooth each color channel  
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      imRef(r, x, y) = imRef(im, x, y).r;
      imRef(g, x, y) = imRef(im, x, y).g;
      imRef(b, x, y) = imRef(im, x, y).b;
    }
  }
  
  image<float> *smooth_r = smooth(r, SIGMA);
  image<float> *smooth_g = smooth(g, SIGMA);
  image<float> *smooth_b = smooth(b, SIGMA);
  
  delete r;
  delete g;
  delete b;
  
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      imRef(im, x, y).r = (int)imRef(smooth_r, x, y);
      imRef(im, x, y).g = (int)imRef(smooth_g, x, y);
      imRef(im, x, y).b = (int)imRef(smooth_b, x, y);
    }
  }
  
  delete smooth_r;
  delete smooth_g;
  delete smooth_b;
#endif

	// Define the interval between seeds and the start seed
	int interW = INTERVAL;
	int interH = INTERVAL;
	int startW = interW / 2;
	int startH = interH / 2;
	regionCounter = 0;


/**************************/
/* Phase 1 agglomération. */
/**************************/

	// Test from the first seed to the last one.

  for (int h = startH; h < height; h+=interH) {
    for (int w = startW; w < width; w+=interW) {
//  for (int h = 0; h < height; h++) {
//    for (int w = 0; w < width; w++) {
      if(imRef(imRegNo, w, h) == 0)
      {
      	regionCounter++;
	      imRef(imRegNo, w, h) = regionCounter;
	      regionCounter = regionCounter;
				imRef(imRegPixSum, (int)regionCounter%width, (int)regionCounter/width)++;
		  	imRef(imRegValSum, (int)regionCounter%width, (int)regionCounter/width)+=calGray(im, w, h);
	      testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regionCounter, w, h);

	      while(p.size()!=0)
	      {
					long temp=p.front();
					p.pop();
	      	testNeighborPixel(im, imRegNo, imRegPixSum, imRegValSum, regionCounter, getW(temp), getH(temp));
	      }
			}
    }
	}

	cout<<"Finish test all seeds"<<" p.seze="<<p.size()<<" regionCounter="<<regionCounter<<endl;


/***************************************/
/* Phase 2 Fusion de région adjacentes */
/***************************************/
#ifdef USE_MERGE
  for (int h = 0; h < height; h++) {
    for (int w = 0; w < width; w++) {
    	if(imRef(imRegNo, w, h) != 0) {
				testNeighborRegion(imRegNo, imRegPixSum, imRegValSum, w, h);
    	}
    }
	}
#endif

	// create output image
  image<rgb> *output = new image<rgb>(width, height);

  // pick random colors for each component
  rgb *colors = new rgb[width*height];
  for (int i = 0; i < width*height; i++)
    colors[i] = random_rgb();
  
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      imRef(output, x, y) = colors[imRef(imRegNo, x, y)];
      
//      if(y<1&&x<50)
//      cout<<x<<" "<<y<<" PixSum:"<<(int)imRef(imRegPixSum, x, y)<<" ValSum:"<<(long)imRef(imRegValSum, x, y)<<" ValGrayIm:"<<calGray(im, x, y)<<endl;
      
    }
  }  

  delete [] colors;  
  delete imRegNo;

	*regNum = regionCounter;
  return output;
}

#endif
